填充数组

[编程题]填充数组

热度指数：4082 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛妹给了牛牛一个长度为 $n$ 的下标从 $0$ 开始的正整型数组 $a$ ，粗心的牛牛不小心把其中的一些数字删除了。

假如 $a_{i}$ 被删除了，则 $a_{i}=0$ 。对于所有被删除的数字，牛牛必须选择一个正整数填充上。现在牛牛想知道有多少种填充方案使得：

$a_{0} \leq a_{1} \leq...\leq a_{n-1}$ 且对于所有的 $0 \leq i \leq n-1$ 满足 $1 \leq a_{i} \leq k$ 。

函数传入一个下标从 $0$ 开始的数组 $a$ 和一个正整数 $k$ ，请返回合法的填充方案数对 $10^9+7$ 取模的值,保证不存在方案数为0的数据。

示例1

输入

[0,4,5],6

输出

说明

所有的合法填充方案是：[1,4,5],[2,4,5],[3,4,5],[4,4,5]，共4种。

示例2

输入

[1,0,0],3

输出

说明

所有的合法填充方案是：[1,1,1],[1,1,2],[1,2,2],[1,2,3],[1,3,3],[1,1,3]共6种

示例3

输入

[0,0,0,0,0,67,0,0],100

输出

746845806

备注:

$1 \leq n,k \leq 1000$

数组 $a$ 满足 $0 \leq a_{i} \leq k$

算法知识视频讲解

Python 3

牛客139289501号

class Solution:
    def FillArray(self , a , k ):
        len1 = len(a)
        dp = [[1]*(len1+1) for _ in range(k+1)]
        for i in range(1, k+1):
            dp[i][1] = i
        for j in range(1, len1+1):
            dp[1][j] = 1

        for i in range(2, k+1):
            for j in range(2, len1+1):
                dp[i][j] = dp[i][j-1] + dp[i-1][j]

        nums = [1]+a+[k]
        len2 = len(nums)
        start = []
        end = []
        for i in range(1, len2-1):
            if nums[i] == 0 and nums[i-1] >0:
                start.append(i)
            if nums[i] == 0 and nums[i+1] >0:
                end.append(i)

        ans = 1       
        for s, e in zip(start, end):
            ans *= dp[min(nums[e+1],k) - nums[s-1]+1][e-s+1]
        return ans%(10**9 + 7)

发表于 2022-09-07 20:41:17 回复(0)